package com.dy.图.最短路径;
//任意两点的距离
//经过第三方点进行调整
public class Floyd {
    private static int N = 1000;
    private static int[][] Graph = {
            {0, 1, 5, N, N, N, N, N, N},
            {1, 0, 3, 7, 5, N, N, N, N},
            {5, 3, 0, N, 1, 7, N, N, N},
            {N, 7, N, 0, 2, N, 3, N, N},
            {N, 5, 1, 2, 0, 3, 6, 9, N},
            {N, N, 7, N, 3, 0, N, 5, N},
            {N, N, N, 3, 6, N, 0, 2, 7},
            {N, N, N, N, 9, 5, 2, 0, 4},
            {N, N, N, N, N, N, 7, 4, 0}};

    public static void main(String[] args) {

        floyd(Graph,8,5);
    }
    static void floyd(int[][] graph,int start ,int end){

        int n=graph.length;

        //path[i][j]=k表示经过i经过k到达j
        int[][] path = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                path[i][j] = j;
            }
        }

        for(int k=0;k<n;k++){
           for(int i=0;i<n;i++){
               for(int j=0;j<n;j++){

                   //graph[i][j] = Math.min(graph[i][j],graph[i][k]+graph[k][j]);
                   if(graph[i][j]>graph[i][k]+graph[k][j]){
                       graph[i][j] = graph[i][k]+graph[k][j];
                       path[i][j] = path[i][k];//经过k
                   }
               }
           }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.printf("%5d",graph[i][j]);
            }
            System.out.println();
        }

        System.out.println("需要走最短"+Graph[start][end]+"步");
        System.out.println();
        while(start!=end){
            System.out.print(start+">>>>>");
            start = path[start][end];
        }
        System.out.println(start);

    }
}
